
/**
 * @file pt_heap2.c
 * @author Linquan  
 * @brief 可以动态分配相同大小的块，如果是需要分配随机大小的块，会出现内存碎片，建议使用heap4。
 *         在第一次分配空间前，会自动进行初始化
 * @version 1.0
 * @date 2024-06-12
 * 
 * @copyright Copyright (c) 2024
 * 
 */

#include "FreeRTOS_heap2.h"

#if  FREE_RTOS_HEAP_2

#include <stdlib.h>
#include <stdint.h>

 #include "color_print.h"

// 总共栈大小，移植敏感
#define TOTAL_HEAP_SIZE     1024
// 字节对齐，移植敏感
#define BYTE_ALIGNMENT      8

// 指针大小，移植敏感
#ifdef __GNUC__
#define POINTER_SIZE_TYPE       uint64_t
#elif defined ARMCC_VERSION
#define POINTER_SIZE_TYPE       uint32_t
#endif

/* 断言，移植敏感 */ 
#define HEAP_ASSERT(expr)  ASSERT_PARAM(expr)
/*关闭线程调度标志位 ，移植敏感 */
#define SUSPEND_ALL() 
/* 恢复线程调度标志，并处理关闭期间的数据，移植敏感*/
#define RESUME_ALL()

/* 字节对齐掩码*/
#define BYTE_ALIGNMENT_MASK     BYTE_ALIGNMENT - 1  
/* 可用堆空间大小 */
#define ADJUSTED_HEAP_SIZE      (TOTAL_HEAP_SIZE - BYTE_ALIGNMENT)

#ifndef USE_MALLOC_FAILED_HOOK
#define USE_MALLOC_FAILED_HOOK 0
#endif

#if USE_MALLOC_FAILED_HOOK
__attribute__((weak)) void app_malloc_failed_hook(void)
{
    for (;;)
        ;
}
#endif

__attribute__((weak)) void heap_lock(void)
{
}

__attribute__((weak)) void heap_unlock(void)
{
}

static void heap_init( void );

static uint8_t s_heap[ TOTAL_HEAP_SIZE ];

typedef struct A_BLOCK_LINK {
    struct A_BLOCK_LINK *next_free_block; /*<< The next free block in the list. */
    size_t block_size;                    /*<< The size of the free block. */
} block_link_t;

/* 根据字节对齐大小计算存储信息的结构体的大小，并进而确定一个内存块的最小长度 */
static const uint16_t heap_struct_size = ((sizeof(block_link_t) + (BYTE_ALIGNMENT - 1)) & ~BYTE_ALIGNMENT_MASK);
#define MINIMUM_BLOCK_SIZE ((size_t)(heap_struct_size * 2)) /* 最小的块尺寸*/

static block_link_t start, end;

static size_t free_bytes_remaining = ADJUSTED_HEAP_SIZE; 

#define insert_block_into_free_list(block_to_insert)                                                                       \
    {                                                                                                                     \
        block_link_t *iterator;                                                                                           \
        size_t block_size;                                                                                                \
                                                                                                                          \
        block_size = block_to_insert->block_size;                                                                         \
                                                                                                                          \
        /* Iterate through the list until a block is found that has a larger size */                                      \
        /* than the block we are inserting. 迭代遍历列表，直到找到一个大小大于我们正在插入块的块 */                                                                            \
        for (iterator = &start; iterator->next_free_block->block_size < block_size; iterator = iterator->next_free_block) \
        {                                                                                                                 \
            /* There is nothing to do here - just iterate to the correct position. */                                     \
        }                                                                                                                 \
                                                                                                                          \
        /* Update the list to include the block being inserted in the correct */                                          \
        /* position.把正在插入的块，插到一个大小 比正在插入块大的块后边 */                                                                                                   \
        block_to_insert->next_free_block = iterator->next_free_block;                                                     \
        iterator->next_free_block = block_to_insert;                                                                      \
    }

void *pt_malloc( size_t size )
{
    block_link_t *block, *previous_block, *new_block_link;
    static long heap_has_been_initialised = 0;
    void *ret = NULL;

    heap_lock();
    {
        /* If this is the first call to malloc then the heap will require
         * initialisation to setup the list of free blocks. */
        if ( heap_has_been_initialised == 0 ) {
            heap_init();
            heap_has_been_initialised = 1;
        }

        /* The wanted size must be increased so it can contain a block_link_t
         * structure in addition to the requested amount of bytes. */
        if ( ( size > 0 ) &&
                ( ( size + heap_struct_size ) >  size ) ) { /* Overflow check */
            size += heap_struct_size; /* 在分配的区域大小以外，还要多分配一块用于存储信息*/

            /* Byte alignment required. Check for overflow.需要字节对齐，检查移除 */
            if ( ( size + ( BYTE_ALIGNMENT - ( size & BYTE_ALIGNMENT_MASK ) ) ) > size ) {
                /* 将取值，修改为按照字节对齐的大小，补上缺的余数 */
                size += ( BYTE_ALIGNMENT - ( size & BYTE_ALIGNMENT_MASK ) );
                HEAP_ASSERT( ( size & BYTE_ALIGNMENT_MASK ) == 0 );
            } else {
                size = 0;
            }
        } else {
            size = 0;
        }


        if ( ( size > 0 ) && ( size <= free_bytes_remaining ) ) {
            /* Blocks are stored in byte order - traverse the list from the start
             * (smallest) block until one of adequate size is found. */
            previous_block = &start;
            block = start.next_free_block;

            /* 遍历查找一块大小足够的块，用于分配 */
            while ( ( block->block_size < size ) && ( block->next_free_block != NULL ) ) {
                previous_block = block;
                block = block->next_free_block;
            }

            /* If we found the end marker then a block of adequate size was not found. */
            if ( block != &end ) {
                /* Return the memory space - jumping over the block_link_t structure
                 * at its start. 返回的空间起始地址，需要越过分配的存信息的块的空间，分配的其实是 block里的空间*/
                ret = ( void * ) ( ( ( uint8_t * ) previous_block->next_free_block ) + heap_struct_size );

                /* This block is being returned for use so must be taken out of the
                 * list of free blocks. 把分配的空间从空闲链表上删掉，就是把block这个节点删掉 */
                previous_block->next_free_block = block->next_free_block;

                /* If the block is larger than required it can be split into two. */
                if ( ( block->block_size - size ) > MINIMUM_BLOCK_SIZE ) {
                    /* This block is to be split into two.  Create a new block
                     * following the number of bytes requested. The void cast is
                     * used to prevent byte alignment warnings from the compiler.
                     * 建一个新块，把block剩下的空间地址和大小记录，然后把这个新块插进空闲链表里 */
                    new_block_link = ( void * ) ( ( ( uint8_t * ) block ) + size );

                    /* Calculate the sizes of two blocks split from the single
                     * block. */
                    new_block_link->block_size = block->block_size - size;
                    block->block_size = size;

                    /* Insert the new block into the list of free blocks. */
                    insert_block_into_free_list( ( new_block_link ) );
                }

                free_bytes_remaining -= block->block_size;
            }
        }
    }
    ( void ) heap_unlock();

#if ( USE_MALLOC_FAILED_HOOK == 1 )
    {
        if ( ret == NULL ) {
            app_malloc_failed_hook();
        }
    }
#endif

    return ret;
}


void pt_free( void *pv )
{
    uint8_t *puc = ( uint8_t * ) pv;
    block_link_t *pxLink;

    if ( pv != NULL ) {
        /* The memory being freed will have an block_link_t structure immediately
         * before it. 将要释放的空间前边还有一个block_link_t的结构，得往前偏移找到真正的头地址 */
        puc -= heap_struct_size;

        /* This unexpected casting is to keep some compilers from issuing
         * byte alignment warnings. */
        pxLink = ( void * ) puc;

        SUSPEND_ALL();/* 关闭线程调度标志位 */
        {
            /* Add this block to the list of free blocks. */
            insert_block_into_free_list( ( ( block_link_t * ) pxLink ) );
            free_bytes_remaining += pxLink->block_size;
        }
        RESUME_ALL();/* 恢复线程调度，且处理期间的数据 */
    }
}

size_t pt_get_free_size( void )
{
    return free_bytes_remaining;
}
/*-----------------------------------------------------------*/

void pt_heap_init( void )
{
    /* This just exists to keep the linker quiet. */
}

static void heap_init( void )
{
    block_link_t *first_free_block;
    uint8_t *aligned_heap;

    /* Ensure the heap starts on a correctly aligned boundary. 
        在分配的堆空间内，找到一个字节对齐的地址*/
    aligned_heap = ( uint8_t * ) ( ( ( POINTER_SIZE_TYPE ) & s_heap[ BYTE_ALIGNMENT ] ) & ( ~( ( POINTER_SIZE_TYPE ) BYTE_ALIGNMENT_MASK ) ) );

    /* start is used to hold a pointer to the first item in the list of free
     * blocks.  The void cast is used to prevent compiler warnings. */
    start.next_free_block = ( void * ) aligned_heap;
    start.block_size = ( size_t ) 0;

    /* end is used to mark the end of the list of free blocks. */
    end.block_size = ADJUSTED_HEAP_SIZE;
    end.next_free_block = NULL;

    /* To start with there is a single free block that is sized to take up the
     * entire heap space. 
     最初，有一个单一的空闲块，其大小足以占据整个堆空间 */
    first_free_block = ( void * ) aligned_heap;
    first_free_block->block_size = ADJUSTED_HEAP_SIZE;
    first_free_block->next_free_block = &end;
}


#endif
